package com.learn.algorlthm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @classname:
 * @Description:二叉树中和为某一值的路径
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-08-03 14:39
 *
 * 题目描述：
 * 输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶
 * 结点所经过的结点形成一条路径。
 */
public class Learn34 {


    private static List<List<Integer>> urls;
    private static List<List<Integer>> urls_res = new ArrayList<>();

    public static List<List<Integer>> backtracking(int num) {
        TreeNode treeNode = getTreeNode();

        backtracking(treeNode ,num);
        return urls_res;
    }

    private static void backtracking(TreeNode treeNode, int num) {
        if (treeNode == null)
            return;

        if (urls == null) {
            urls = new ArrayList<>();
            urls.add(new ArrayList<>());
        }
        List<Integer> nextList = new ArrayList<>(urls.get(urls.size() - 1));
        nextList.add(treeNode.value);
        urls.add(nextList);

        num -= treeNode.value;
        if (num == 0)
            urls_res.add(nextList);

        int leftNum = num, rightNum = num;
        backtracking(treeNode.left, leftNum);
        backtracking(treeNode.right, rightNum);

        System.out.println(urls.toString());
        urls.remove(urls.size() - 1); //想不到这一步，参考了资料（可以注释看看）

    }





    public static TreeNode getTreeNode() {
//        int[] values = {1 ,2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 ,18, 19, 20};
        int[] values = {1 ,2, 3, 4, 5, 6, 7};

        LinkedList<TreeNode> list = new LinkedList<>();
        for (int value : values) {
            list.add(new TreeNode(value));
        }

        for (int preIndex = 0; preIndex < values.length/2 -1; preIndex++) {

            TreeNode node = list.get(preIndex);
            node.left = list.get(preIndex *2 + 1);
            node.right = list.get(preIndex * 2 + 2);
        }

        int lastIndex = values.length/2 - 1;
        list.get(lastIndex).left = list.get(lastIndex * 2 +1);
        if (values.length % 2 != 0)
            list.get(lastIndex).right = list.get(lastIndex * 2 +2);


        return list.get(0);
    }

    static class TreeNode{
        public int value;

        public TreeNode left;
        public TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int value) {
            this.value = value;
        }
    }


}
